package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"time"
)

//快速排序
func QuickSortString(arr []string) []string {
	length := len(arr) //数组长度
	if length <= 1 {
		return arr
	} else {

		splitdata := arr[0]          //以第一个为基准
		low := make([]string, 0, 0)  // 存储比基准小的
		high := make([]string, 0, 0) // 存储比基准大的
		mid := make([]string, 0, 0)  // 与我相等的

		//加入第一个相等
		mid = append(mid, splitdata)

		for i := 1; i < length; i++ {
			if arr[i] < splitdata {
				low = append(low, arr[i])
			} else if arr[i] > splitdata {
				high = append(high, arr[i])
			} else {
				mid = append(mid, arr[i])
			}

		}

		low, high = QuickSortString(low), QuickSortString(high) //切割递归

		myarr := append(append(low, mid...), high...) // 小拼接相等， 在拼接大的
		return myarr

	}
}

//插入排序
func InsertSortString(arr []string) []string {
	length := len(arr) //数组长度
	if length <= 1 {
		return arr
	} else {
		for i := 1; i < length; i++ { //跳过第一个
			temp := arr[i]
			j := i - 1 //上一个位置循环找到位置插入
			for j >= 0 && temp < arr[j] {
				arr[j+1] = arr[j] //从前往后移动
				j--
			}
			// fmt.Println(temp)
			arr[j+1] = temp

			if j > 200000 {
				break
			}

		}
		return arr
	}
}

// 计算排序时间
func main() {
	t1 := time.Now()
	const N = 6428632               //需要开辟的内存
	allstrs := make([]string, N, N) //存放
	fmt.Println(len(allstrs))       //开辟数组存储数据

	fi, err := os.Open("D:\\go\\csdnemail.txt")
	if err != nil {
		fmt.Println("文件读取失败", err)
		return
	}
	defer fi.Close() //延迟关闭文件

	// 读取文件内容
	bf := bufio.NewReader(fi)
	i := 0
	linestr := ""
	for {
		line, _, err := bf.ReadLine()
		if err == io.EOF {
			break
		}
		linestr = string(line)
		allstrs[i] = linestr
		i++
	}

	use := time.Since(t1)
	fmt.Println("数据读取耗时", use)
	//数据读取完毕
	fmt.Println("数据读取完毕，开始排序")

	// 快速排序
	/**
	6428632
	数据读取耗时 544.0311ms
	数据读取完毕，开始排序
	数据排序耗时 22.624294s
	*/
	//allstrs = QuickSortString(allstrs)

	// 插入排序
	/**
	只有20万数据
	数据读取耗时 642.0367ms
	数据读取完毕，开始排序
	数据排序耗时 3m41.9296936s
	*/
	allstrs = InsertSortString(allstrs)

	use2 := time.Since(t1)
	fmt.Println("数据排序耗时", use2)

	path := "D:\\go\\csdnemail33.txt"

	savefile, _ := os.Create(path)
	defer savefile.Close()

	save := bufio.NewWriter(savefile) //对象用于写入

	for i := 0; i < len(allstrs); i++ {

		fmt.Fprintln(save, allstrs[i])

	}

	save.Flush()

}
